前言

此篇主要為writeup跟歐幾里得算法相關筆記
會解以下兩題，開始吧（￣︶￣）↗　

Writeup

Greatest Common Divisor

題目

網址 : https://cryptohack.org/courses/modular/gcd/

思路

這題要我們求出a, b兩數的公因數，可利用輾轉相除法(歐幾里得算法)來解

解法1

• code

a = 66528
b = 52920

while(b != 0):
    temp = a % b
    a = b
    b = temp
print(a)

解法2

利用python math函式庫中的gcd()

• code

import math
print(math.gcd(66528, 52920))

簡單多惹XD

• Output
  

flag : 1512

Extended GCD

題目

網址 : https://cryptohack.org/courses/modular/egcd/

思路

利用擴展歐幾里得算法得出u跟v，flag為數值最小的

解法

python -m pip install egcd

from egcd import egcd
p = 26513
q = 32321
print(egcd(32321,26513))

• Output
  

flag : -8404

統整筆記

• 歐幾里得算法(輾轉相除法，來源：https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/euclidean_algorithm.html)
  
  34先跟10除，得到餘數4後10再去跟4除，得到餘數2後再去跟4除，最後得到0結束
  設兩數a, b 且a > b, 商為q, 餘數為r, mod用"%"代替
  輾轉流程(讓a永遠都是被除數) :

1. r = a%b
2. a = b
3. b = r
4. 如果b為0就結束，否則回到第1點
5. 最後b為兩數最大公因數

• 擴展歐幾里得算法(擴展輾轉相除法)
  a * u + b * v = gcd(a,b)，利用此算法求u跟v
  貝祖定理 : ax + by = gcd(a, b)
  過程 : (來源 : https://ccjou.wordpress.com/2012/11/16/%E5%88%A9%E7%94%A8%E5%9F%BA%E6%9C%AC%E5%88%97%E9%81%8B%E7%AE%97%E5%AF%A6%E7%8F%BE%E6%93%B4%E5%B1%95%E6%AD%90%E5%B9%BE%E9%87%8C%E5%BE%97%E6%BC%94%E7%AE%97%E6%B3%95/)
  

小結

今天複習了輾轉相除法跟學到了擴展歐幾里得算法，有點小難，不過還是有去理解一下惹(但函式庫真滴好用XD)明天繼續下面兩題!

參考資料

擴展歐幾里得算法 : https://zh.wikipedia.org/zh-tw/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95
擴展歐幾里得算法(影片講解) : https://www.youtube.com/watch?v=hB34-GSDT3k&t=2s&ab_channel=GVSUmath
輾轉相除法 :　https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/euclidean_algorithm.html